package leet209subarrayminsizebysw

// 如下算法在使用了左右指针构成的滑动窗口，
// 右指针主动扩大窗口，以便找到符合条件的子数组，一旦找到后，左指针尝试缩小窗口看看有没有更小的符合条件的子数组，没有的话，就继续扩大窗口。
func MinSubArrayLen(target int, nums []int) int {
	// 1. 定义一个变量来记录最小的长度
	minLength := len(nums) + 1
	// 2. 定义一个变量来记录当前的和
	sum := 0
	// 3. 定义一个变量来记录左指针的位置
	left := 0
	// 4. 遍历数组，右指针从0到len(nums)-1
	//    寻找一个固定的窗口右侧
	for right := 0; right < len(nums); right++ {
		// 5. 将当前元素加入到sum中
		sum += nums[right]
		// 6. 当sum大于等于target时，此时窗口中的区间满足条件，更新minLength，但是我们并不知道是否该窗口的子窗口会更适合，
		//    所以我们继续缩小窗口，检查是否有更小的符合条件的子数组。
		//    缩小的时候记得将sum减去左指针的元素，然后再缩小。
		for sum >= target {
			minLength = min(minLength, right-left+1)
			sum -= nums[left]
			left++
		}
	}
	if minLength == len(nums)+1 {
		return 0
	}
	return minLength
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// 复杂度分析
// 时间复杂度：O(n)，其中n是数组的长度。我们只需要遍历一次数组。
// 空间复杂度：O(1)，我们只需要常数的空间来存储变量。
